package momo.multitree.algo;

import momo.multitree.structure.*;

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Vector;


public class EdmundAlgo
{
	private Node root;
	private Graph g;
	private HashMap<Node, Edge> inEdges;
	private HashMap<Edge, Edge> mapEdges;
	private Vector<Edge> allEdges;
	HashMap<Edge, HashMap<Node, Double>> mapWeights;
	
	public EdmundAlgo(Graph g)
	{
		this.g = g;
		inEdges = new HashMap<Node, Edge>();
		mapEdges = new HashMap<Edge, Edge>();
		allEdges = new Vector<Edge>();
		mapWeights = new HashMap<Edge, HashMap<Node, Double>>();
	}
	
	public Tree optimumTree()
	{
		//dun allow nodes that has no edges
		if ( !g.isConnectedGraph() )
			return null;
		
		//find the root that has the smallest stability
		initRoot();
		// init all mapping of edges
		initMapEdges();
		// init all the weights
		initWeights();
		//find all the min incoming edge of each node except root
		initInEdge();
		// remove inner cycles and attach to min incoming till no cycles left
		Vector<Node> cycleNode;
		while ( (cycleNode=detectCycle()).size() != 0 )
			removeCycle(cycleNode);
		
//		Tree tree = new Tree(root);
//		for(Edge edge: allEdges)
//		{
//			System.out.println(edge.toString());
//			tree.add(mapEdges.get(edge));
//		}
		
		Graph graph = new Graph();
		for(Edge edge: allEdges)
			graph.add(mapEdges.get(edge));
		
		Tree tree = new Tree(root, graph);
		
		return tree;
	}
	
	private void initRoot()
	{
		double min = Double.POSITIVE_INFINITY;
		for(Node node: g.getNodes())
		{
			double stab = node.getStability(); 
			if ( stab < min )
			{
				min = stab;
				root = node;			
			}
		}
	}
	
	private void initMapEdges()
	{
		for(Edge e: g.getEdges())
			mapEdges.put(e, e);
	}
	
	private void initWeights()
	{
		for(Node parent: g.getNodes())
		{
			for(Edge e: g.getEdgesOfNode(parent))
			{
				Node child = e.nextNode(parent);
				this.setWeights(e, parent, parent.getStability());
//				weights.setPair(parent, child, parent.getStability());
			}
		}
	}
	
	private void initInEdge()
	{
		HashSet<Node> nodeVisited = new HashSet<Node>();
		nodeVisited.add(root);
		
		//put all the edges from root
		// (2) <- (R)
		// nodeVisited.put( node2, edge );
		for(Edge edgeFromRoot: g.getEdgesOfNode(root))
		{
			Node node = edgeFromRoot.nextNode(root);
			inEdges.put(node, edgeFromRoot);
			allEdges.add(edgeFromRoot);
			nodeVisited.add(node);
		}
		
		// put the min incoming edge for the rest of nodes
		for(Node child: g.getNodes())
		{
			if ( !nodeVisited.contains(child) )
			{
				nodeVisited.add(child);
				
				double min = Double.POSITIVE_INFINITY;
				
				for(Edge edgeFromChildNode: g.getEdgesOfNode(child) )
				{
					Node parent = edgeFromChildNode.nextNode(child);
//					double stability = weights.getPair(parent, child);
					double stability = getWeights(edgeFromChildNode, parent);
					if ( stability < min )
					{
						min = stability;
						inEdges.put(child, edgeFromChildNode);
					}
				}
				allEdges.add(inEdges.get(child));
			}
		}
	}
	
	private Vector<Node> detectCycle()
	{
		
		Vector<Node> cycle = new Vector<Node>();
		HashSet<Node> nodeVisited = new HashSet<Node>();
		Vector<Node> toVisit = new Vector<Node>();
		
		// for every node traversal
		for(Node node: g.getNodes())
		{
			boolean hasVisitedContracted = false;
			// only checks the path if its not yet visited
			if ( !nodeVisited.contains(node) )
			{
				//add to toVisit
				toVisit.add(node);
				
				while ( !toVisit.isEmpty() )
				{
					Node child = toVisit.remove(0);
					
					cycle.add(child);
					nodeVisited.add(child);
					
					Edge incomingEdge = inEdges.get(child);
					if ( incomingEdge != null )
					{
						Node parent = incomingEdge.nextNode(child);
						if ( cycle.contains(parent) )
						{
							int index = cycle.indexOf(parent);
							for(int i=0; i<index; i++)
								cycle.removeElementAt(0);
							return cycle;
						}else
							toVisit.add(parent);
					}
				}
				cycle.clear();
			}
		}
		return cycle;
	}
	
	private void removeCycle(Vector<Node> cycleNode)
	{
		double minWeight = Double.POSITIVE_INFINITY;
		Edge toAdd = null;
		Edge toRemove = null;
		Node affectedCycleNode = null;
		
		double minInCycle = minCycleWeights(cycleNode);		
		
		for(Node cycNode: cycleNode)
		{
			for(Edge possibleEdgeToAdd: g.getEdgesOfNode(cycNode))
			{
				Node parent = possibleEdgeToAdd.nextNode(cycNode);
				if ( cycleNode.contains( parent ) )
					continue;
				
				Edge incomingEdgeInCycle = inEdges.get(cycNode);
				Node parentInCycle = incomingEdgeInCycle.nextNode(cycNode);
//				double cycleWeight = weights.getPair(parentInCycle, cycNode);
				double cycleWeight = getWeights(incomingEdgeInCycle, parentInCycle);
//				double newWeight = weights.getPair(parent, cycNode) - ( cycleWeight - minInCycle );
				double newWeight = getWeights(possibleEdgeToAdd, parent) - ( cycleWeight - minInCycle );
				
//				weights.setPair(parent, cycNode, newWeight);
				setWeights(possibleEdgeToAdd, parent, newWeight);
				if ( newWeight < minWeight )
				{
					minWeight = newWeight;
					toAdd = possibleEdgeToAdd;
					toRemove = incomingEdgeInCycle;
					affectedCycleNode = cycNode;
				}
			}
		}
		
		inEdges.put(affectedCycleNode, toAdd);
		allEdges.remove(toRemove);
		allEdges.add(toAdd);
		
		//after processing removal of cycle edges and insertion of out edges to cycle
		
		StringBuffer id = new StringBuffer();
		HashSet<Node> setOfNodesInContractedGraph = new HashSet<Node>();
		for(Node cycNode: cycleNode)
		{
			id.append("-"+cycNode.getId());
			setOfNodesInContractedGraph.add(cycNode);
		}
		if (id.capacity() > 1)
			id.deleteCharAt(0);
		
		Node contractedNode = new Node(id.toString(), 1, 1);
		
		Graph newGraph = new Graph();
		
		for(Edge e: g.getEdges())
		{
			Node head = e.getHeadNode();
			Node tail = e.getTailNode();
			
			if ( setOfNodesInContractedGraph.contains(head) && setOfNodesInContractedGraph.contains(tail) )
			{
				//ignore this edge since it will be contracted into one
				//remove inEdges of contracted nodes
				if ( inEdges.get(head) == e )
					inEdges.remove(head);
				if ( inEdges.get(tail) == e )
					inEdges.remove(tail);
			}else if ( setOfNodesInContractedGraph.contains(head) )
			{
				Edge newEdge = new Edge(e.getId(), contractedNode, tail, 1, 1, 1, 1);
				mapEdges.put(newEdge, mapEdges.get(e));
				newGraph.add(newEdge);
				
				if ( inEdges.get(head) == e )
					inEdges.put(contractedNode, newEdge);
				if ( inEdges.get(tail) == e )
					inEdges.put(tail, newEdge);
				
//				weights.setPair(contractedNode, tail, weights.getPair(head, tail) );
				setWeights(newEdge, contractedNode, getWeights(e, head));
//				weights.setPair(tail, contractedNode, weights.getPair(tail, head) );
				setWeights(newEdge, tail, getWeights(e, tail));
				
//				int index = allEdges.indexOf(e);
//				if ( index >= 0 )
//					allEdges.set(index, newEdge);
				
			}else if ( setOfNodesInContractedGraph.contains(tail) )
			{
				Edge newEdge = new Edge(e.getId(), head, contractedNode, 1, 1, 1, 1);
				mapEdges.put(newEdge, mapEdges.get(e));
				newGraph.add(newEdge);
				
				if ( inEdges.get(head) == e )
					inEdges.put(head, newEdge);
				if ( inEdges.get(tail) == e )
					inEdges.put(contractedNode, newEdge);
				
//				weights.setPair(head, contractedNode, weights.getPair(head, tail));
				setWeights(newEdge, head, getWeights(e, head));
//				weights.setPair(contractedNode, head, weights.getPair(tail, head));
				setWeights(newEdge, contractedNode, getWeights(e, tail));
				
//				int index = allEdges.indexOf(e);
//				if ( index >= 0 )
//					allEdges.set(index, newEdge);
				
			}else
			{
				//normal edge
				newGraph.add(e);
			}
		}
		g = newGraph;
		
//		for(Edge e: mapEdges.keySet())
//		{
//			System.out.println("key: " + e.toString());
//			System.out.println("value: " + mapEdges.get(e).toString());
//		}
//		System.out.println("\n\n");
		
	}
	
	private double minCycleWeights(Vector<Node> cycleNode)
	{
		double min = Double.POSITIVE_INFINITY;
		
		for(Node child: cycleNode)
		{
			Edge e = inEdges.get(child);
			Node parent = e.nextNode(child);
//			double stability = weights.getPair(parent, child);
			double stability = getWeights(e, parent);
			if ( stability < min )
				min = stability;
		}
		
		return min;
	}
	
	private double getWeights(Edge edge, Node from)
	{
		HashMap<Node, Double> pairsSet = mapWeights.get(edge);
		return pairsSet.get(from);
	}
	
	private void setWeights(Edge edge, Node from, double value)
	{
		HashMap<Node, Double> pairsSet = mapWeights.get(edge);
		if ( pairsSet == null )
		{
			pairsSet = new HashMap<Node, Double>();
			mapWeights.put(edge, pairsSet);
		}
		pairsSet.put(from, value);		
	}
	
}//end of class EdmundAlgo
